package org.example.leetcpde;

import org.junit.jupiter.api.Test;

public class longestPalindrome {

    @Test
    void longestPalindrome() {
        System.out.println(longestPalindrome("babad"));
    }

    public String longestPalindrome(String s) {
        if (s == null) {
            return null;
        }

        if (s.length() == 1) {
            return s;
        }

        byte[] bytes = s.getBytes();
        int len = bytes.length;
        boolean[][] dp = new boolean[len][len];
        int max = 1, begin = 0;
        for(int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (bytes[i] == bytes[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (j - i + 1 > max) {
                        max = j - i + 1;
                        begin = i;
                    }
                }
            }
        }

        return s.substring(begin, begin + max);
    }
}
